ABC015 D - 高橋くんの苦悩
https://atcoder.jp/contests/abc015/tasks/abc015_4
提出
code: python
w = int(input())
n, k = map(int, input().split())
ab = list(map(int, input().split())) for _ in range(n)
print(ab)
dp = [-1 * (w+1) for _ in range(k+1)]
dp00 = 0
解答
code: python
w = int(input())
n, k = map(int, input().split())
ab = list(map(int, input().split())) for _ in range(n)
# k枚使った時の重要度の最大値を保持
dp = [[0 * (w + 1) for _ in range(k + 1)] for _ in range(n)]
for i in range(n):
for ki in range(1, k + 1):
for wi in range(w + 1):
# 幅, 重要度
a, b = abi
if wi - a >= 0:
dpikiwi = max(dpikiwi, dpi-1ki-1wi-a + b)
dpikiwi = max(dpikiwi, dpi-1kiwi)
print(dp-1-1-1)
code: python
w = int(input())
n, k = map(int, input().split())
ab = list(map(int, input().split())) for _ in range(n)
# k枚使った時の重要度の最大値を保持
dp = [0 * (w + 1) for _ in range(k + 1)]
for i in range(n):
for ki in range(k, 0, -1):
for wi in range(w, -1, -1):
# 幅, 重要度
a, b = abi
if wi - a >= 0:
dpkiwi = max(dpkiwi, dpki-1wi-a + b)
print(dp-1-1)
テーマ
#dp
蟻本 2-3 01ナップサック問題
メモ
DP(動的計画法)で次元を減らすテクニック
LIS でも大活躍! DP の配列使いまわしテクニックを特集